#pragma once
#include <iostream>
#include <assert.h>
#include <algorithm>
#include <initializer_list>
using namespace std;
namespace wu
{
    template <class T>
    struct list_node
    {
        list_node<T> *_next;
        list_node<T> *_prev;
        T _data;

        list_node(const T &x = T())
            : _next(nullptr),
              _prev(nullptr),
              _data(x)
        {
        }
    };

    template <class T, class Ref, class Ptr>
    class list_iterator
    {
        typedef list_node<T> Node;
        typedef list_iterator<T, Ref, Ptr> Self;

    public:
        Node *_node;
        list_iterator(Node *node)
            : _node(node)
        {
        }

        Ref operator*()
        {
            return _node->_data;
        }

        Ptr operator->()
        {
            return &_node->_data;
        }

        Self &operator++()
        {
            _node = _node->_next;
            return *this;
        }

        Self &operator--()
        {
            _node = _node->_prev;
            return *this;
        }

        Self operator++(int)
        {
            Self temp(*this);
            _node = _node->_next;
            return temp;
        }

        Self operator--(int)
        {
            Self temp(*this);
            _node = _node->_prev;
            return temp;
        }

        bool operator!=(const Self &it) const
        {
            return _node != it._node;
        }

        bool operator==(const Self &it) const
        {
            return _node == it._node;
        }
    };

    template <class T>
    class list
    {
        typedef list_node<T> Node;

    public:
        typedef list_iterator<T, T &, T *> iterator;
        typedef list_iterator<const T, const T &, const T *> const_iterator;
        iterator begin()
        {
            return iterator(_head->_next);
        }

        iterator end()
        {
            return iterator(_head);
        }

        size_t size()
        {
            return _size;
        }

        void empty_init()
        {
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;
            _size = 0;
        }

        list()
        {
            empty_init();
        }

        list(initializer_list<T> It)
        {
            empty_init();
            for (const auto &e : It)
            {
                push_back(e);
            }
        }

        list(const list<T> &It)
        {
            empty_init();
            for (const auto &e : It)
            {
                push_back(e);
            }
        }

        void Swap(list<T> &It)
        {
            swap(_head, It._head);
            swap(_size, It._size);
        }

        list<T> &operator=(list<T> It)
        {
            Swap(It);
            return *this;
        }

        void insert(iterator pos, const T &x)
        {
            Node *cur = pos._node;
            Node *prev = cur->_prev;
            Node *newnode = new Node(x);
            newnode->_prev = prev;
            newnode->_next = cur;
            prev->_next = newnode;
            cur->_prev = newnode;
            _size++;
        }

        void push_back(const T &x)
        {
            insert(end(), x);
        }

        void push_front(const T &x)
        {
            insert(begin(), x);
        }

        iterator erase(iterator it)
        {
            assert(it != end());
            Node *cur = it._node;
            Node *prevnode = cur->_prev;
            Node *nextnode = cur->_next;
            prevnode->_next = nextnode;
            nextnode->_prev = prevnode;

            delete cur;
            _size--;
            return iterator(nextnode);
        }

        void pop_front()
        {
            erase(begin());
        }

        void pop_back()
        {
            erase(end());
        }

        void clear()
        {
            iterator it = begin();
            while (it != end())
            {
                it = erase(it);
            }
        }

        ~list()
        {
            clear();
            delete _head;
            _head = nullptr;
        }

    private:
        Node *_head;
        size_t _size;
    };
}
